1. Field of the Invention
The present invention relates generally to a program cache apparatus, and, more particularly, to an apparatus for caching programs in a memory to quickly invoke a program in the computer system which executes demand paging type storage management.
2. Description of the Related Art
Recently, a large-capacity memory can be connected as a main storage device to relatively small computer systems because the prices of semiconductor memories gradually become cheaper. Therefore, it is demanded that operating systems (hereinafter called "OS's") which control such computers have a function to effectively use a large-capacity memory. That is, there is a demand for the function which efficiently caches a program or data on an external storage device like a hard disk onto such a large-capacity main memory. Here "cache" means to read data or a program stored in a slow memory, though having large capacity, such as a hard disk, to be executed by a central processing unit, and to hold it in a fast main memory for quick execution of this program next time.
As computer systems become more complex, it is demanded that programs that run on the systems are efficiently developed and maintained. Accordingly, programs are often divided into small modules and stored in an external storage device in the module form. In this case, at the time a program is execute, those many modules are relocated or combined on the main memory and are then run by a central processing unit. In this aspect, therefore, there is also a demand for efficient caching of programs on the main memory.
To meet those demands, many cache systems have been proposed conventionally.
There is an OS which employs a demand paging system, for example, as one of those cache systems. In such an OS, a memory is managed page frame by page frame which is a minute divided memory area (physical page) of a fixed length. A program is also divided into pages of the same size. In such an OS, part of pages which are necessary for a process that is performed in the central processing unit are selected and cached page by page on the memory among pages that constitute a program stored on an external storage device.
More specifically, when invoking of a program is requested by a process ("process" here is a process in a multitask, i.e., a task or an execution unit, and is hereinafter used as such), the correlation between the storage status in the logical space that is secured on the memory for that process and the storage locations of pages constituting this program on an external storage device is checked page by page. Simply invoking a program does not load the pages of the program into page frames on the memory. If the physical page for a page exists in the page cache in the memory (i.e., if this page has already been loaded from the external storage device) when this page is actually accessed, this physical page is mapped in the logical space of that process (i.e., an address translation table is set to translate the designation of the logical address from the process to the designation of a physical address, so that the physical address from the process is accessible from the process). If the physical page for the page in question is not present in the page cache, a new physical page is secured, the contents of that page from the external storage device are written on the new physical page to locate the physical page in the page cache. At the same time, the physical page is mapped in the logical space of the process.
The physical page on the page cache and the physical page allocated to the process are shared by a copy-on-write means. The copy-on-write means is accomplished in the following manner. While reading from the physical page by the process is permitted (reading is possible without copying), writing is disabled. When a request to write on the physical page is made by the process, an interruption occurs. In the interrupt process, the contents of the physical page are copied on a new and different page, this new page is allocated to the process this time and writing is enable. According to this copy-on-write, even if the contents of the physical page allocated to the process are altered, the contents of the original physical page can be left unchanged to be ready for an access from another process.
When a program is loaded, an OS should relocate the program and link the program to the system library before a process actually executes that program (i.e., the instruction portion and data portion of the program). According to the conventional demand paging system,. those relocation and linkage are executed in the process space after the setting for the copy-on-write is completed.
The detail of the program relocation will now be discussed. Programs stored in an external storage device are designed on the premise that they are mapped in the logical space that has a specific range of addresses (logical addresses). For instance, in the example shown in FIG. 11, it is assumed that a program stored in an external storage device is mapped in the logical space starting at the address 1000. Therefore, a jump subroutine instruction in the instruction portion of the program is set to jump to the address 1300 which is considered within that program range. When an OS loads this program as predicted as shown in FIG. 11, relocation need not be executed. On the premise that a process loads a plurality of programs, however, there is no guarantee that a program is loaded at the predicted address. When a program is loaded at an address other than the predicted one as shown in FIG. 12, therefore, if the jumping address in the jump subroutine instruction is left unchanged, a jump is made to the address 1300 which is not associative to this program at all. To avoid this problem, the OS refers to the relocation table as shown in FIG. 14 and rewrites the jumping address to the correct address within the program range as shown in FIG. 13.
The linkage to the system library will now be described. Programs stored in an external storage device may be designed on the assumption that they refer to subroutines in the system library stored in the external storage device. In the example shown in FIG. 15, for instance, a jump subroutine instruction is set at the address 1044 of the loaded program. In the initial state, however, a dummy address "00000000" is written at the jumping address in this jump subroutine instruction, as shown in FIG. 15. Before executing the program in the process space, the OS refers to the linkage table (FIG. 18) in the program and writes the head address of some subroutine in the system library (FIG. 17) at the jumping address, as shown in FIG. 16.
If the contents of a page are not rewritten by the execution of a program, i.e., if the process merely reads the contents of a program, simply mapping the physical page mapped on the page cache onto the process space allows this physical page to be shared by the page cache and the process space. However, the execution of a program actually rewrites the page. In particular, since the data area of the program is written by the execution of the program, the physical page is also rewritten. When the program is executed next time, therefore, malfunction occurs.
On the assumption that the contents of a page are rewritten, the contents of a program loaded onto the physical page may be copied on another physical page, which is then mapped in the process space. In this case, however, two pages with the same contents that will not be rewritten would exist redundantly, thus reducing the efficiency usage of memory.
According to the conventional demand paging system, therefore, when a program loaded onto a physical page from an external storage device is mapped in the process space, only the copy-on-write setting is carried out.
But, the relocation of a program and linkage of the program to the system library, which will be executed subsequently, inevitably include writing processes. The writing processes generate an interrupt, so that the physical page where this program is loaded is inevitably copied. The physical page should thus always be doubled, lowering the efficiency of memory usage.
According to the conventional demand paging system, the relocation of a program and linkage of the program to the system library are executed in the process space. When the same program is invoked again, therefore, the physical page where this program is loaded is mapped in the process space by the setting of the copy-on-write. It is thus necessary to execute similar program relocation and program linkage to the system library again, resulting in a poor processing efficiency. Further, since relocation information and linkage information on the external storage device are referred to in the program relocation and linkage to the system library at the time the program is invoked again, I/O processing is required, considerably increasing the processing time.